#include<iostream>
#include<algorithm>
using namespace std;

// 最大连续字段和 https://www.acwing.com/solution/content/110854/
const int N = 5e5;
int a[N], n, m;

struct Node
{
    int l, r;
    int tmax, lmax, rmax;
    int sum;
}t[4*N];

void pushup(Node& u, Node& l, Node& r)
{
    u.sum = l.sum + r.sum;
    u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.rmax = max(r.rmax, r.sum + l.rmax);
}

void pushup(int u)
{
    pushup(t[u], t[u << 1], t[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    t[u].l = l, t[u].r = r;
    if(l == r)
    {
        t[u].tmax = t[u].lmax = t[u].rmax = t[u].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

// a[i]修改为k
void modify(int u, int i, int k)
{
    if(t[u].l == t[u].r)
    {
        t[u].tmax = t[u].lmax = t[u].rmax = t[u].sum = k;
        return;
    }
    int mid = (t[u].l + t[u].r) >> 1;
    if(i <= mid)
        modify(u << 1, i, k);
    else
        modify(u << 1 | 1, i, k);
    pushup(u);
}

Node quary(int u, int l, int r)
{
    if(t[u].l >= l && t[u].r <= r) 
        return t[u];
    int mid = (t[u].l + t[u].r) >> 1;
    if(l > mid) return quary(u << 1 | 1, l, r);
    else if(r <= mid) return quary(u << 1, l, r);
    else
    {
        auto le = quary(u << 1, l, r);
        auto ri = quary(u << 1 | 1, l, r);
        Node ret;
        pushup(ret, le, ri);
        return ret;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    build(1, 1, n);
    int op, x, y;
    while(m--)
    {
        scanf("%d%d%d", &op, &x, &y);
        if(op == 1)
        {
            if(x > y) swap(x, y);
            auto ret = quary(1, x, y);
            printf("%d\n", ret.tmax);
        }
        else
        {
            modify(1, x, y);
        }
    }
    return 0;
}
